package problems.daily.y2021m7;

import java.util.HashMap;
import java.util.Map;

/**
 * @author habitplus
 * @since 2021-07-07 09:21
 */
public class T20210707N1 {
    // 1711. 大餐计数
    // 大餐 是指 恰好包含两道不同餐品 的一餐，其美味程度之和等于 2 的幂。
    // 你可以搭配 任意 两道餐品做一顿大餐。
    // 给你一个整数数组 d ，其中 d[i] 是第 i 道餐品的美味程度，
    // 返回你可以用数组中的餐品做出的不同 大餐 的数量。结果需要对 10^9 + 7 取余。
    // 注意，只要餐品下标不同，就可以认为是不同的餐品，即便它们的美味程度相同。
    //
    // 提示：
    //      1 <= d.length <= 105
    //      0 <= d[i] <= 220
    //
    // 题目链接：https://leetcode-cn.com/problems/count-good-meals/
    public int countPairs(int[] deliciousness) {
        final int mod = 1000000007;
        int maxVal = 0;
        int minVal = Integer.MAX_VALUE;
        for (int val : deliciousness) {
            maxVal = Math.max(maxVal, val);
            minVal = Math.min(minVal, val);
        }
        int maxSum = maxVal * 2;
        int minSum = minVal * 2;
        int pairs = 0;
        Map<Integer, Integer> map = new HashMap<>();
        int n = deliciousness.length;
        for (int val : deliciousness) {
            for (int sum = minSum; sum <= maxSum; sum <<= 1) {
                int count = map.getOrDefault(sum - val, 0);
                pairs = (pairs + count) % mod;
            }
            map.put(val, map.getOrDefault(val, 0) + 1);
        }
        return pairs;
    }

    public static void main(String[] args) {
        System.out.println(new T20210707N1().countPairs(new int[]{1,1,1,3,3,3,7}));
    }
}
